package alogrithm.solution;

import java.util.Arrays;

/*
 * 5.查找最小的k个元素
 题目：输入n个整数，输出其中最小的k个。
 例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
 */
public class P5 {
	//O(kn)
	public static int[] findKMinEle(int array[], int k) {
		if (k >= array.length)
			return array;
		int result[] = new int[k];
		for (int i = 0; i < k; i++) 
			result[i] = array[i];
		for(int i=k;i<array.length;i++)
		{
			int max = Integer.MIN_VALUE;
			int max_index=-1;
			for(int j=0;j<k;j++)
			{
				if(result[j]>max)
				{
					max=result[j];
					max_index=j;
				}
			}
			if(array[i]<max)
			{
				result[max_index]=array[i];
			}
		}
		return result;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int array[]={4,3,8,2,1,6,7,5};
		int result[]=findKMinEle(array, 4);
		for(int i:result)
			System.out.print(i+"\t");

	}

}
